package com.acwing;

import com.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 是否对称树
 */
public class No39 {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        while (!list.isEmpty()) {
            int start = 0;
            int end = list.size() - 1;
            while (start <= end) {
                if (list.get(start) != null && list.get(end) != null && list.get(start).val != list.get(end).val) {
                    return false;
                } else if (list.get(start) == null && list.get(end) != null) {
                    return false;
                } else if (list.get(end) == null  && list.get(start) != null) {
                    return false;
                }
                start++;
                end--;
            }
            List<TreeNode> temp = new ArrayList<>();
            for (TreeNode treeNode : list) {
                if (treeNode == null) {
                    continue;
                }
                temp.add(treeNode.left);
                temp.add(treeNode.right);
            }
            list = temp;
        }
        return true;
    }
}
